﻿// 5154. 牛的基因学.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/5157/

贝茜最近正在学习基因学，具体来说她正在研究 DNA
 序列比对。

DNA
 序列字符串是指由字符 A、C、G、T 组成的字符串。

设字符串 s
 和 t
 是两个长度为 n
 的 DNA
 序列字符串。

将函数 h(s,t)
 定义为在字符串 s
 和 t
 中，字符相同的位置数量。

利用函数 h(s,t)
 进一步定义 DNA
 距离函数 ρ(s,t)
：

ρ(s,t)=∑i=0n−1∑j=0n−1h(shift(s,i),shift(t,j))
其中，shift(s,i)
 表示将字符串 s
 循环左移 i
 位后得到的字符串。

例如：

ρ(“TCG”,”GCA”)=

h(“TCG”,”GCA”)+h(“TCG”,”CAG”)+h(“TCG”,”AGC”)+

h(“CGT”,”GCA”)+h(“CGT”,”CAG”)+h(“CGT”,”AGC”)+

h(“GTC”,”GCA”)+h(“GTC”,”CAG”)+h(“GTC”,”AGC”)=

1+1+0+0+1+1+1+0+1=6
现在，给定一个长度为 n
 的 DNA
 序列字符串 s
，请你统计一共有多少个长度为 n
 的 DNA
 序列字符串 t
 与字符串 s
 的 DNA
 距离达到最大可能值。

更形象地说，请你计算一共有多少个长度为 n
 的 DNA
 序列字符串 t
 满足：ρ(s,t)=maxu:|u|=|s|ρ(s,u)
。

由于结果可能很大，你只需要输出对 109+7
 取模后的结果。

输入格式
第一行包含整数 n
。

第二行包含一个长度为 n
 的由字符 A、C、G、T 组成的字符串，表示字符串 s
。

输出格式
一个整数，表示对 109+7
 取模后的结果。

数据范围
前 3
 个测试点满足 1≤n≤3
。
所有测试点满足 1≤n≤105
。

输入样例1：
1
C
输出样例1：
1
输入样例2：
2
AG
输出样例2：
4
输入样例3：
3
TTT
输出样例3：
1
*/
int main()
{
    std::cout << "Hello World!\n";
}

 